class Solution(object):
    def shortestPalindrome(self, s):
        """
        :type w: str
        :rtype: str
        """
        w = s + '#' + s[::-1]
        t = [0]*len(w)
        t[0] = 0
        pos = 1
        sz = 0
        while pos<len(w):
            while sz>0 and w[pos]!=w[sz]:
                sz = t[sz-1]
            if w[pos]==w[sz]: sz+=1
            t[pos]=sz
            pos+=1
            
        length = len(s)-t[-1]
        return s[-1:-length-1:-1] + s

print(Solution().shortestPalindrome("aacecaaa"))